Signals passed on a communication channel between a transmitter and a receiver can be affected by noise or interfered by signals on adjacent channels. One objective of channel encoding and decoding is to protect signals against errors caused by noise or interference. Convolutional codes have been used extensively in digital communications in order to incorporate forward error correction into a transmitted message. FIG. 1 illustrates a typical convolutional encoder 100 that includes a first latch 102, a second latch 104, and various adders 106, 108 and 110. The latch 102 receives an input signal from node C, and generates an output signal at node B. The latch 104 receives an input signal from node B, and generates an output signal at node A. The output X equals to the summation of signals at nodes C, B and A. The output Y equals to the summation of signals at nodes C and A. In this example, for each bit arriving at node C, two bits are generated at X and Y. The X and Y bits can be decoded by using a trellis diagram, which is comprised of a set of nodes representing logics states of the latches 102 and 104, and a set of links showing the progression of the logic states as the convolutional encoder 100 continues receiving input signals at node C.
One important issue in decoding convolutional codes is trellis termination. Conventionally, there are two methods to terminate the trellis of convolutional codes. One common method is to force the convolutional encoder to a known state by flushing it with a given input sequence, e.g. series of zero inputs. This approach simplifies the decoder design. However, one drawback of the approach is the rate loss due to these additional tail bits.
Tail biting, which designates the same values to the beginning and ending states of a trellis diagram, is another method typically used for trellis termination. Since tail biting does not require any additional bits, it does not have the rate loss problem. However, due to the uncertainty of the beginning and ending states, the calculation of tail biting codes can be very complex. Thus, various sub-optimum decoders have been proposed for tail biting codes, where the decoder performance is compromised to avoid high computational complexity.
As such, what is needed is a sub-optimum decoding scheme that properly balances the decoder performance and computational complexity for tail-biting convolution codes.